Aminet 7/Aminet 7 - August 1995.iso/Aminet/docs/misc/ConcNews.lha/news/general.programming/comp.programming_2212_000028.msg

Text File | 1994-11-27 | 2.0 KB | 47 lines

Newsgroups: comp.programming
From: [e-mail] (Lawrence Kirby)
Path: dd.chalmers.se!news.chalmers.se!sunic!pipex!demon!genesis.demon.co.uk!fred
Subject: Re: Conservative Sorting/Presv Order of Orig??
References: <[e-mail]>
Organization: none
Reply-To: [e-mail]
X-Newsreader: Demon Internet Simple News v1.27
Lines: 33
Date: Sun, 24 Apr 1994 15:26:17 +0000
Message-ID: <[e-mail]>
Sender: [e-mail]

In article <[e-mail]>
           [e-mail] "Robert H. Cudmore" writes:

>Hello all,
>
>        I am attempting to sort an array of elements A.  I have a Heap sort
>up and running, the problem is this:  I need the elements with equal keys
>to remain in their original order.  Heap sort with building(hiring) and
>Sorting(firing) of the array into a heap and then into a sorted array seems
>to cause the destruction of the original order of all elements.

Sorts which preserve the order of equal keys are described as 'stable' sorts.

>        Are there efficient O(nlogn) sorting routines that will preserve this
>original order?  Quicksort seems to do the same destructive ordering of
>the data where as a simple insertion sort does not.  I would like to stay
>away from linear complexity sorts and would also like to know if I can't
>stay away from them.

Heapsort and Quicksort are not stable. Mergesort is stable, guaranteed O(nlogn)
in the worst case and is just about the fastest of the O(nlogn) sorts. However
if you are sorting arrays rather than lists it requires extra workspace (e.g.
an extra array of n pointers).

You can always make any sort stable by adding a secondary key for
each element which you initialise in ascending order before starting the
sort.

--
-----------------------------------------
Lawrence Kirby | [e-mail]
Wilts, England | [e-mail]
-----------------------------------------